#include "os_mem.h"
#include "os_sched.h"
//#include "os_mutex.h"

#define MEM_MIN_SIZE            4
#define MEM_ITEM_SIZE           MEM_HIGH_ALIGED(sizeof(os_mem_item_t), MEM_ALIGN_BYTES)

#if !OS_MEM_DBG_PRINT_ENABLE
#undef os_dbg
#define os_dbg(fmt, ...) do {}while (0)    // 不用do while，用空代码也宏
#endif

#if OS_MEM_ENABLE

//static os_mutex_t mem_mutex;            // 分配内存所用的互斥信号量
/**
 * 初始化
 */
static void mem_item_init (os_mem_item_t * item, int data_size) {
    item->used = 0;
    item->data_size = data_size;
    os_list_item_init(&item->item, os_mem_item_t, item);
}

/**
 * 判断能否合并
*/
static inline int mem_item_can_merge (os_mem_item_t * pre, os_mem_item_t * after) {
    int merge;

    merge = (uint8_t *)pre + MEM_ITEM_SIZE + pre->data_size == (uint8_t *)after;
    return merge;
}

/**
 * 合并两个内存块（只调整大小，不调整链接）
*/
static inline void mem_item_merge (os_mem_item_t * item1, os_mem_item_t * item2) {
    item1->data_size += MEM_ITEM_SIZE + item2->data_size;
}

#if OS_MEM_INFO_ENABLE
/**
 * 获取空闲的堆总大小
*/
int os_get_free_size (void) {
    int total_size = 0;

    os_list_for_each(curr, os_mem_item_t, &os_core.heap_mem.list) {
        total_size += curr->data_size;
    }

    return total_size;
}
#endif // OS_MEM_INFO_ENABLE

/**
 * 初始化内存堆
 * @param start_mem 堆起始地址
 * @param size 堆的大小
*/
os_err_t os_mem_init (void) {
    static uint8_t start_mem[OS_MEM_ALLOC_SIZE];

    os_assert(OS_MEM_ALLOC_SIZE >= (MEM_ITEM_SIZE + MEM_MIN_SIZE));
    os_dbg("init heap: %x, size: %d\n", (int)start_mem, OS_MEM_ALLOC_SIZE);

    // 计算初始可用的内存地址和总大小
    uint8_t * heap_start = (uint8_t *)MEM_HIGH_ALIGED(start_mem, MEM_ALIGN_BYTES);     // 起始地址必须进行对齐
    uint8_t * heap_end = (uint8_t *)MEM_LOW_ALIGED(start_mem + OS_MEM_ALLOC_SIZE, MEM_ALIGN_BYTES);

    uint32_t data_size = (uint32_t)(heap_end - heap_start);                 // 可分配空间大小，结果是对齐的

    // 将前面的块加入空闲队列
    os_list_init(&os_core.heap_mem.list, os_mem_item_t, item);
    os_dbg("adjust heap: %x, size: %d\n", (int)heap_start, (int)(data_size));
   os_core.heap_mem.heap_start = heap_start;   // 整个堆起始地址
    os_core.heap_mem.heap_size = data_size;   // 整个堆起始地址

   // 初始化空闲结构的起始和结束
    os_mem_item_t * first_item = (os_mem_item_t *)heap_start;
    mem_item_init(first_item, data_size - MEM_ITEM_SIZE);
    os_list_insert_first(&os_core.heap_mem.list, first_item);

    // 互斥锁初始化
    //os_mutex_init(&mem_mutex);
    return OS_ERR_OK;
}

/**
 * 将空闲的item加入到空闲列表中
*/
static void insert_to_mem_list (os_mem_item_t * free_item) {
    // 特殊情况，没有空闲结点，简单加入链表即可
    if (os_list_count(&os_core.heap_mem.list) == 0) {
        os_list_insert_first(&os_core.heap_mem.list, free_item);
        return;
    }

    // 有多个空闲块的按地址增序排列的内存块, 找到地址比free大的结点
    os_list_for_each(heigher_item, os_mem_item_t, &os_core.heap_mem.list) {
        if ((uint8_t *)heigher_item > (uint8_t *)free_item) {
            break;
        }
    }

    if (heigher_item == OS_NULL) {
        // 当前item为最后的，尝试与末结点合并，或者插入到最后
        os_mem_item_t * last_item = (os_mem_item_t *)os_list_last(&os_core.heap_mem.list);
        if (mem_item_can_merge(last_item, free_item)) {
            mem_item_merge(last_item, free_item);
        } else {
            os_list_insert_after(&os_core.heap_mem.list, last_item, free_item);
        }
    } else {
        // 找到地址更高的项，插入其前面并进行合并
        // 尝试与前一个块进行合并
        os_mem_item_t * pre_item = os_list_item_pre(&os_core.heap_mem.list, heigher_item);
        if (pre_item != OS_NULL) {
            // 如果能合并，则将前一个结点移出去进行合并，这样形成一个新的大的空闲块
            if (mem_item_can_merge(pre_item, free_item)) {
                // 将其移出去，作为一个新的空闲块，方便在下面可能与后面的块进行合并
                os_list_remove_item(&os_core.heap_mem.list, pre_item);

                // 合并两个空闲块
                mem_item_merge(pre_item, free_item);

                free_item = pre_item;
                pre_item = os_list_item_pre(&os_core.heap_mem.list, heigher_item);
            }
        }

        // 再尝试与后一个块进行合并
        if (mem_item_can_merge(free_item, heigher_item)) {
            os_list_remove_item(&os_core.heap_mem.list, heigher_item);  // 先将后面的移除

            mem_item_merge(free_item, heigher_item);    // 合并

            if (pre_item) {
                os_list_insert_after(&os_core.heap_mem.list, pre_item, free_item);
            } else {
                os_list_insert_first(&os_core.heap_mem.list, free_item);
            }
        } else {
            // 不能合并，插入到其前边
            os_list_insert_after(&os_core.heap_mem.list, pre_item, free_item);
        }
    }
}

/**
 * 从堆中分配内存
*/
void * os_mem_malloc (int size) {
    os_param_failed(size == 0, OS_NULL);

    void * free_addr = OS_NULL;

    // 进行对齐，从而使得后续的item能够自然地进行对齐
    int request_size = MEM_HIGH_ALIGED(size, MEM_ALIGN_BYTES);

    //mem_alloc_lock();

    //  预先检查，避免不必要的错误
    //os_mem_check();

    // 遍历整个链表, 找首个匹配的项，采用首次匹配算法。也可以修改下面的循环，更改成其它算法
    os_list_for_each(curr, os_mem_item_t, &os_core.heap_mem.list) {
        // 大小足够，直接跳过
        if (curr->data_size >= request_size) {
            break;
        }
    }

    // 找到大小匹配的块，此时先将基从链表中移除，分配前面部分，后半部分再插入列表
    if (curr) {
        os_list_remove_item(&os_core.heap_mem.list, curr);  // 先将后面的移除

        // 从当前块中去掉多余的空间
        int free_size = curr->data_size - request_size;
        if (free_size >= (int)(MEM_MIN_SIZE + MEM_ITEM_SIZE)) {
            os_mem_item_t * unused_item = (os_mem_item_t *)(((uint8_t *)curr + MEM_ITEM_SIZE) + request_size);

            // 初始化后，加入空闲列表中
            mem_item_init(unused_item, free_size - MEM_ITEM_SIZE);
            insert_to_mem_list(unused_item);

            // 当可以分割时，data_size去掉多余的空间
            curr->data_size = request_size;
        }

        // 当前块分配出去
        os_list_item_init(&curr->item, os_mem_item_t, item);
        //curr->pre = curr->next = curr;
        curr->used = 1;
        free_addr = (uint8_t *)curr + MEM_ITEM_SIZE;        // 返回值

        //os_mem_check();

	    os_dbg("alloc memory: %x, %d - %d\n", (int)free_addr, size, curr->data_size);
    } else {
        os_dbg("alloc memory failed: size %d.\n", size);
    }

    //mem_alloc_unlock();
    return free_addr;
}

/**
 * 释放内存到堆中
*/
os_err_t os_mem_free (void * mem) {
    os_param_failed(mem == OS_NULL, OS_ERR_PARAM);
    os_dbg("free: %x\n", (int)mem);

    os_mem_item_t * mem_item = (os_mem_item_t *)((uint8_t *)mem - MEM_ITEM_SIZE);
    os_assert(mem_item->used == 1);
    os_assert(mem_item->data_size >= MEM_MIN_SIZE);

    os_mem_item_t * pre = os_list_item_pre(&os_core.heap_mem.list, mem_item);
    os_mem_item_t * next = os_list_item_next(&os_core.heap_mem.list, mem_item);
    os_assert(next == OS_NULL);
    os_assert(pre == OS_NULL);

    // 发现已经未被占用，且pre, next有误，则有问题
    if (!mem_item->used
            || (pre && (os_list_item_next(&os_core.heap_mem.list, pre) != mem_item))
            || (next && (os_list_item_pre(&os_core.heap_mem.list, next) != mem_item))
            || (mem_item->data_size < MEM_MIN_SIZE)) {
        os_dbg("mem item error, not used or pre and next error\n");
        return OS_ERR_STATE;
    }

    // 进行释放工作
    mem_item->used = 0;             // 标记为未被占用

    // 加收到内存队列中，并注意检查
    insert_to_mem_list(mem_item);
    return OS_ERR_OK;
}

#endif
